/*
 * @lc app=leetcode.cn id=678 lang=typescript
 *
 * [678] 有效的括号字符串
 */

// @lc code=start
function checkValidString(s: string): boolean {
  const m = s.length;
  const leftStack = [];
  const starStack = [];

  // 利用双栈处理括号匹配
  for (let i = 0; i < m; i++) {
    const char = s[i];
    if (char === '(') {
      leftStack.push(i);
    } else if (char === '*') {
      starStack.push(i);
    } else {
      if (leftStack.length) {
        leftStack.pop();
      } else if (starStack.length) {
        starStack.pop();
      } else {
        return false;
      }
    }
  }

  // 双栈中可能还留有元素
  // 这个时候需要将'('和'*'做匹配。并且'('下标小于'*'
  while (leftStack.length && starStack.length) {
    const leftIdx = leftStack.pop();
    const starIdx = starStack.pop();
    if (leftIdx > starIdx) return false;
  }

  return leftStack.length === 0;
}
// @lc code=end
